/**
 * 316. 去除重复字母
 * https://leetcode-cn.com/problems/remove-duplicate-letters/
 */
public class Solutions_316 {
    public static void main(String[] args) {
//        String str = "bcabc";  // output: "abc"
        String str = "cbacdcbc";  // output: "acdb"

        String result = removeDuplicateLetters(str);
        System.out.println(result);
    }

    public static String removeDuplicateLetters(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        // lastMap[0] = 2，字符 a 在 s 中最后出现的位置是索引 2，用于判断某字符是否在当前遍历索引之后存在
        int[] lastMap = new int[26];
        // visitMap[0] = true，字符 a 已经添加到结果集中，不能添加重复字符
        boolean[] visitMap = new boolean[26];
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            lastMap[arr[i] - 'a'] = i;
        }

        char[] stack = new char[arr.length];
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            char a = arr[i];
            if (visitMap[a - 'a']) {
                // 不能重复添加
                continue;
            }
            while (idx > 0 && stack[idx - 1] > a && lastMap[stack[idx - 1] - 'a'] > i) {
                // 当前字符小于栈顶字符，且栈顶字符可以删除时（即索引 i 之后，还存在栈顶字符时）
                visitMap[stack[idx - 1] - 'a'] = false;
                idx --;
            }
            // 字符入栈，并标记为已添加
            stack[idx++] = a;
            visitMap[a - 'a'] = true;
        }
        return new String(stack, 0, idx);
    }
}
